
function heapSort(arr){
	const n = arr.length
	const lastNode = n - 1
	const parent = Math.floor((lastNode - 1)/2)

	//构建堆
	for(let i = parent; i>=0; i --){
		heapify(arr, n , i)
	}
	//排序
	for(let i = lastNode; i > 0 ; i--){
		swap(arr, 0, i)
		heapify(arr, i, 0)
	}
	return arr
}

function heapify(arr, n , i){
	let max = i
	let left = i * 2 + 1
	let right = i * 2 + 2
	if(n > left && arr[left]>arr[max]){
		max = left		
	}
	if(n > right &&arr[right]>arr[max]){
		max = right
	}

	if(max !== i){
		swap(arr, i, max)
		heapify(arr, n, max)
	}
}

function swap(arr, i, j){
	[arr[i], arr[j]]=[arr[j], arr[i]]
}

const arr = [8,7,4,5,10,9,3,2,6,1]
const res = heapSort(arr)
console.log(res,'🍉')